package com.south.base.test.arithmetic.dynamic.programming;

import org.junit.Assert;
import org.junit.Test;

/**
 * 观光组合
 *
 * @author Administrator
 * @date 2020/6/17 9:21
 */
public class SightseeingPair {
    /**
     * 给定正整数数组 A，A[i] 表示第 i 个观光景点的评分，并且两个景点 i 和 j 之间的距离为 j - i。
     * 一对景点（i < j）组成的观光组合的得分为（A[i] + A[j] + i - j）：景点的评分之和减去它们两者之间的距离。
     * 返回一对观光景点能取得的最高分。
     */
    @Test
    public void maxScoreSightseeingPair() {
        Assert.assertEquals(11, maxScoreSightseeingPair(new int[]{8, 1, 5, 2, 6}));
    }

    public int maxScoreSightseeingPair(int[] A) {
        int ans = 0,
                // 标识最大的前置
                // A[i] + A[j] + i - j = A[i] + i + (A[j] - j)
                // 当 A[i] + i和A[j] - j最大时，才是得分最高
                // 但j一直在改变，只能记录最大的A[i] + i
                mx = A[0];
        for (int j = 1; j < A.length; ++j) {
            ans = Math.max(ans, mx + A[j] - j);
            // 边遍历边维护
            mx = Math.max(mx, A[j] + j);
        }
        return ans;
    }
}
